import numpy as np

def is_magic(M_list):
    M = np.array(M_list) # Превращаем в массив numpy
    n = len(M)

    # Собираем все суммы в одно множество:
    # 1. Сумма главной диагонали: np.trace(M) или sum(M.diagonal())
    # 2. Сумма побочной: sum(np.fliplr(M).diagonal())
    # 3. Суммы строк: np.sum(M, axis=1)
    # 4. Суммы столбцов: np.sum(M, axis=0)

    # В лекции использовался подход со срезами и генераторами:
    s_diag1 = sum(M[i, i] for i in range(n))
    s_diag2 = sum(M[i, n-1-i] for i in range(n))
    s_rows = {sum(M[i, :]) for i in range(n)} # Срез строки i
    s_cols = {sum(M[:, j]) for j in range(n)} # Срез столбца j

    all_sums = {s_diag1, s_diag2} | s_rows | s_cols
    return len(all_sums) == 1

from collections import defaultdict
from copy import copy

def get_factors(n):
    # 1. Сначала находим один простой делитель для каждого числа (как в решете)
    # L[i] хранит минимальный простой делитель числа i
    min_prime = [0] * (n + 1)
    for i in range(2, n + 1):
        if min_prime[i] == 0:
            for j in range(i, n + 1, i):
                if min_prime[j] == 0: min_prime[j] = i

    # 2. Динамически строим словари разложений
    # Разложение числа i = Разложение (i // p) + множитель p
    factors = [defaultdict(int) for _ in range(n + 1)]

    for i in range(2, n + 1):
        p = min_prime[i]
        # Берем разложение меньшего числа (копируем!)
        prev_factors = factors[i // p]
        factors[i] = copy(prev_factors)
        # Добавляем текущий делитель
        factors[i][p] += 1

    return factors

cache = {}
def power_cached(a, n):
    key = (a, n) # Ключ - кортеж аргументов
    if key not in cache:
        if n == 0: return 1
        if n % 2 == 0:
            # a^n = (a^(n/2))^2
            half = power_cached(a, n // 2)
            cache[key] = half * half
        else:
            cache[key] = a * power_cached(a, n - 1)
    return cache[key]

memo = {}
def max_palindrome(s):
    if s in memo: return memo[s]
    if len(s) <= 1: return s
    if s[0] == s[-1]:
        res = s[0] + max_palindrome(s[1:-1]) + s[-1]
    else:
        p1 = max_palindrome(s[:-1])
        p2 = max_palindrome(s[1:])
        res = p1 if len(p1) > len(p2) else p2
    memo[s] = res
    return res

class Cache:
    def __init__(self, func):
        self.func = func
        self.memory = {}

    def __call__(self, n):
        if n not in self.memory:
            self.memory[n] = self.func(n)
        return self.memory[n]

    def __getitem__(self, n): # Позволяет писать fib[10]
        return self.__call__(n)

@Cache
def fib(n):
    if n <= 2: return 1
    return fib(n-1) + fib(n-2)

# Вызов: print(fib(10)) или print(fib[10])

class Function:
    def __init__(self, func):
        self.func = func

    def __call__(self, x):
        return self.func(x)

    def __mul__(self, other):
        # Возвращаем новую "Функцию", которая применяет self к результату other
        def composition(x):
            return self.func(other(x))
        return Function(composition)

@Function
def square(x): return x * x

@Function
def inc(x): return x + 1

# (x+1)^2 для x=2 -> 3^2 = 9
h = square * inc
print(h(2)) 

def curry(func):
    def curried(a):
        def inner(b):
            return func(a, b)
        return inner
    return curried

@curry
def add(a, b):
    return a + b

add_5 = add(5) # Функция, прибавляющая 5
print(add_5(10)) # 15

class Expr:
    def __init__(self, left, op, right):
        self.left, self.op, self.right = left, op, right

    def __call__(self): # Вычисление происходит ЗДЕСЬ
        l_val = self.left() if callable(self.left) else self.left
        r_val = self.right() if callable(self.right) else self.right
        if self.op == '+': return l_val + r_val

class Var:
    def __init__(self, val): self.val = val
    def __call__(self, new_val=None):
        if new_val is not None: self.val = new_val
        return self.val
    def __add__(self, other):
        return Expr(self, '+', other)

x = Var(10)
y = Var(20)
f = x + y   # Выражение создано, но не вычислено
print(f())  # 30
x(50)       # Меняем x
print(f())  # 70 (формула пересчиталась)

class RegistryMeta(type):
    def __init__(cls, name, bases, attrs):
        if not hasattr(cls, 'instances'):
            cls.instances = [] # Создаем список в каждом новом классе
        super().__init__(name, bases, attrs)

class Base(metaclass=RegistryMeta):
    def __init__(self):
        self.__class__.instances.append(self)

class A(Base): pass
class B(Base): pass

a = A()
b = B()
print(A.instances) # [a]
print(B.instances) # [b]

import asyncio

async def async_fib(n):
    a, b = 0, 1
    for _ in range(n):
        await asyncio.sleep(0.1) # Имитация асинхронной задержки
        yield a
        a, b = b, a + b

async def main():
    async for val in async_fib(5):
        print(val)

# Запуск: asyncio.run(main())

# Ключ кеша: (y, x, L) - координаты левого верхнего угла и размер
cache = {}

def max_zeros_square(M, y=0, x=0, L=None):
    if L is None: L = len(M)
    state = (y, x, L)

    if state not in cache:
        # 1. Проверяем текущий квадрат (с помощью генератора и all)
        is_full_zeros = all(M[r][c] == 0 for r in range(y, y+L) for c in range(x, x+L))

        if is_full_zeros:
            cache[state] = L
        else:
            # 2. Если нет, рекурсивно ищем в 4-х вложенных, уменьшая размер L-1
            # Важно: граничные условия рекурсии должны быть обработаны (L=0 -> 0)
            if L <= 1: 
                cache[state] = 0 # Квадрат 1x1 не из нуля -> размер 0
            else:
                res = max(
                    max_zeros_square(M, x, y, L-1),
                    max_zeros_square(M, x+1, y, L-1),
                    max_zeros_square(M, x, y+1, L-1),
                    max_zeros_square(M, x+1, y+1, L-1)
                )
                cache[state] = res

    return cache[state]